#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

class SubsequenceChecker {
public:
    // 构造函数，预处理目标字符串 T
    SubsequenceChecker(const string& T) {
        // 构建字符到位置的映射
        for (int i = 0; i < T.size(); ++i) {
            charIndex[T[i]].push_back(i);
        }
    }

    // 检查 S 是否是 T 的子序列
    bool isSubsequence(const string& S) {
        int lastPos = -1;  // 记录上一个字符的位置
        for (char ch : S) {
            if (charIndex.find(ch) == charIndex.end()) {
                return false;  // T 中没有该字符，直接返回 false
            }
            
            // 在 T 中查找 ch 的下一个出现位置
            const vector<int>& indices = charIndex[ch];
           // 返回值：Iterator to the first element of the range [first, last) ordered after value, or last if no such element is found.
            auto it = upper_bound(indices.begin(), indices.end(), lastPos);
            
            if (it == indices.end()) {
                return false;  // 找不到满足条件的位置
            }
            
            lastPos = *it;  // 更新 lastPos 为当前字符的匹配位置
        }
        return true;
    }

private:
    unordered_map<char, vector<int>> charIndex;  // 字符到位置的映射
};

int main() {
    string T = "abcde";
    
    // 预处理 T
    SubsequenceChecker checker(T);
    
    // 测试
    vector<string> testStrings = {"a", "ab", "ace", "aec", "xyz"};
    
    for (const string& S : testStrings) {
        if (checker.isSubsequence(S)) {
            cout << S << " is a subsequence of " << T << endl;
        } else {
            cout << S << " is NOT a subsequence of " << T << endl;
        }
    }
    
    return 0;
}


/*
代码解释：
SubsequenceChecker 类：

构造函数：预处理字符串 T，将 T 中每个字符的位置存储到 charIndex 中。charIndex 是一个哈希表，键是字符，值是该字符在 T 中的所有位置（一个位置的列表）。
isSubsequence 函数：对于每个输入字符串 S，检查它是否是 T 的子序列。通过遍历 S 中的字符，使用 upper_bound 查找每个字符在 T 中的下一个出现位置。lastPos 用来保证每个字符出现在 T 中的顺序。
二分查找：

对于 T 中的每个字符，charIndex 中记录了它在 T 中的所有位置。当我们遍历 S 时，我们需要找到该字符在 T 中出现的下一个位置。我们使用 upper_bound 来执行二分查找，从而高效地找到符合条件的位置。

性能分析：
预处理时间：预处理 T 的时间复杂度为 O(m)，其中 m 是 T 的长度。我们遍历 T 中的每个字符，并将其位置记录下来。
查询时间：对于每个字符串 Si，我们遍历其中的字符，且每次查找字符的位置时，使用二分查找，时间复杂度是 O(log n)，其中 n 是 T 中该字符出现的次数。
总时间复杂度：假设有 k 个查询，且每个查询的最大长度为 l，则查询的总时间复杂度是 O(k * l * log n)，其中 n 是字符在 T 中出现的最大次数。
优势：
预处理加速查询：通过预处理 T 中的字符位置，我们将查询的时间复杂度从线性降低到了对数级别（O(log n)）。
适用于大规模输入：这种方法非常适合大规模输入（例如 k 可以达到 10 亿），因为预处理 T 后，每个查询只需要较少的计算量。

*/
